// 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，
// 找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，
// 并以列表形式返回。
// 你可以按 任意顺序 返回这些组合。
// candidates 中的 同一个 数字可以 无限制重复被选取 。
// 如果至少一个数字的被选数量不同，则两种组合是不同的。 


// 回溯算法:
// 是一种通过尝试所有可能的组合来找到问题解的算法
// 时间复杂度:(O(n^m),空间复杂度：最坏情况下为 O(target)

function combinationSum(candidates, target) {
  const result = [];

  const dfs = (start, currentCombination, currentSum) => {
    // 如果当前和等于目标值，说明找到了一个有效的组合，将当前组合加入结果数组
    if (currentSum === target) {
      result.push([...currentCombination]);
      return;
    }
    // 如果当前和大于目标值，停止搜索
    if (currentSum > target) {
      return;
    }
    // 从 start 开始遍历 candidates 数组
    for (let i = start; i < candidates.length; i++) {
      // 选择当前数字
      currentCombination.push(candidates[i]);
      // 递归调用，继续寻找组合，由于可以重复使用数字，所以下一次递归的 start 仍然是 i
      dfs(i, currentCombination, currentSum + candidates[i]);
      // 回溯，撤销选择
      currentCombination.pop();
    }
  };
  dfs(0, [], 0);
  return result;
}

// 测试示例
const candidates = [2, 3, 6, 7];
const target = 7;
console.log(combinationSum(candidates, target));    